import java.util.*;
/**
 * Ford-Fulkerson algorithm
 * @author 捣蛋鬼x
 *
 */
public class FF {
	/**
	 * Find maxflow of flownetworks using FF algorithm
	 * @param G Input SimpleGraph
	 * @param s source point
	 * @param t sink point
	 * @return maxflow of the graph
	 * @throws Exception
	 */
	public static int maxFlow(SimpleGraph G, Vertex s, Vertex t) throws Exception{
		SimpleGraph risidual;
		int flow, current, maxcap;
		Iterator i;
		Edge e;
		Vertex v, previous;
		VertexData vdata = new VertexData();
		EdgeData edata;

		flow = 0;
		maxcap = 0;

		for (i = G.edges();i.hasNext(); ){
			e = (Edge) i.next();
			try {
				 edata = new EdgeData(((Double)e.getData()).intValue(),0);
			} catch (Exception e2) {
				// TODO: handle exception
				System.out.println("stop");
				return 0;
			}
			e.setData(edata);
			maxcap = Math.max(maxcap, edata.getCapacity());
		}
		//Find max capacity
			for (i = G.vertices(); i.hasNext(); ){
				v = (Vertex) i.next();
				vdata.setVisited(false);
				v.setData(vdata);			
			}
			//Find a path from s to t
			risidual = FindPath.DFS(G, s, t, new SimpleGraph(), 0);		

			while (risidual.numEdges() > 0){

				current = maxcap;
				previous = s;
				for (i = risidual.edges(); i.hasNext(); ){
					e = (Edge) i.next();
					edata = (EdgeData) e.getData();
					//Find bottle neck
					if (e.getFirstEndpoint() == previous){
						current = Math.min(current, edata.getAvailable());
						previous = e.getSecondEndpoint();
					} else {
						current = Math.min(current, edata.getFlow());
						previous = e.getFirstEndpoint();
					}

				}

				previous = s;
				//Reset available capacity of each edge in residual graph
				for (i = risidual.edges(); i.hasNext(); ){
					e = (Edge) i.next();
					edata = (EdgeData) e.getData();
					if (e.getFirstEndpoint() == previous){
						edata.setFlow(edata.getFlow()+ current);
						previous = e.getSecondEndpoint();
					} else {
						edata.setFlow(edata.getFlow() - current);
						previous = e.getFirstEndpoint();
					}

				}
				flow += current;//Add current flow to flow
				//Set all vertices to be unvisited
				for (i = G.vertices(); i.hasNext(); ){
					v = (Vertex) i.next();
					vdata = (VertexData) v.getData();
					vdata.setVisited(false);			
				}
				risidual = FindPath.DFS(G, s, t, new SimpleGraph(),0);
			}

		return flow;
	}
	
	public static void main(String[] args) throws Exception{
		SimpleGraph G = new SimpleGraph();
		Vertex s = null, t = null;
		Edge e;
		int flow;
		Iterator i;
		EdgeData edata;
		VertexData vdata;
		
//		System.out.print("Please enter the full path and file name for the input data: ");
//      String userinput;
//      userinput = KeyboardReader.readString();
//		GraphInput.LoadSimpleGraph(G,userinput);


		GraphInput.LoadSimpleGraph(G, "Bipartite/s1000-t1000-min1-max100.txt");

		for (i= G.vertices(); i.hasNext(); ) {
            Vertex v = (Vertex) i.next();
            if (v.getName().equals("s")) s=v;
            else if (v.getName().equals("t")) t=v;
            }
		//get the running time
		long startTime=System.currentTimeMillis();
		flow = maxFlow(G, s, t);
		long endTime=System.currentTimeMillis();

		////show the flow in each edge
//		System.out.println("After iterate the flow in each edge");
//		for (i = G.edges(); i.hasNext();) {
//			e = (Edge) i.next();
//			edata = (EdgeData) e.getData();
//			System.out.println("Edge: " + " " + e.getFirstEndpoint().getName()
//					+ "-" + e.getSecondEndpoint().getName() + " "
//					+ edata.getFlow() + "/" + edata.getCapacity());
//		}
		System.out.println("running time�� " + (endTime - startTime) + "ms");
		System.out.println("max flow: " + flow);


	}
}
